import java.lang.reflect.Array;
import java.util.Arrays;

public class Solution714 {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int[] tmpDP = new int[]{-prices[0], 0};// 0:持有 1:不持有
        for (int i = 1; i < n; i++) {
            int maxHold = Math.max(tmpDP[0], tmpDP[1] - prices[i]);
            int maxNotHold = Math.max(tmpDP[0] + prices[i] - fee, tmpDP[1]);
            tmpDP[0] = maxHold;
            tmpDP[1] = maxNotHold;
        }
        return Math.max(tmpDP[0], tmpDP[1]);
    }

    public static void main(String[] args) {
        Solution714 s=new Solution714();
        System.out.println(s.maxProfit(new int[]{1,3,2,8,4,9},2));
    }
}
